package com.topcoder.srm512;

import java.util.HashMap;
import java.util.Set;

/**
 * Ash and Elsh invented a new variant of the game Rock-Paper-Scissors called 
 * DoubleRoshambo. In the normal game, each of the two players change their 
 * right hand into one of these gestures: rock, paper, or scissors. Rock beats 
 * scissors; scissors beat paper; paper beats rock. For example, if Ash plays 
 * rock and Elsh plays paper, then Elsh wins.
 *
 * In DoubleRoshambo, each player uses both hands. Each hand may play different 
 * gestures. A player scores:
 *
 *  2 points, if his right hand beats his opponent's right hand, and his left 
 *    hand beats his opponent's left hand.
 *  1 point, if his right hand beats his opponent's right hand, and his left 
 *    hand plays the same gesture as his opponent's left hand.
 *  0 points, in all other cases.
 *
 * Ash and Elsh played DoubleRoshambo several rounds. You are given two 
 * String[]s A and E, representing the gestures that Ash and Elsh played, 
 * respectively. Each element of A and E will contain two characters. The first 
 * character is for their left hand and the second character is for their 
 * right hand. For each hand, the character will be one of 'R', 'P', or 'S', 
 * representing rock, paper, or scissors, respectively.
 * 
 * However, the gestures are given in no specific order. Return the maximum 
 * points Ash could have possibly scored.
 * 
 * [Algorithm] This is special MaxFlow problem:
 * 1. Any pair score 2 points, it must be selected.
 * 2. Any pair score 1 point, A and E are one-to-one mapping according to score rule. 
 *    So we can choose any edge to solve this max-flow special case.
 */
public class DoubleRoshambo {
	private HashMap<Character, Character> win;
	
	public DoubleRoshambo() {
		win = new HashMap<Character, Character>();
		win.put('R', 'S');
		win.put('S', 'P');
		win.put('P', 'R');
	}
	
	public int maxScore(String[] A, String[] E) {
		int score = 0;
		int N = A.length;
		Counter a = new Counter();
		Counter e = new Counter();
		for (int i=0; i<N; i++) {
			a.add(A[i]);
			e.add(E[i]);
		}
		
		for (String key : a.keySet()) {
			score += a.deductCommon(key, e, score2(key)) * 2;
		}
		
		for (String key : a.keySet()) {
			score += a.deductCommon(key, e, score1(key));
		}
		
		return score;
	}
	
	private String score2(String key) {
		char[] c = key.toCharArray();
		c[0] = win.get(c[0]);
		c[1] = win.get(c[1]);
		return new String(c);
	}
	
	private String score1(String key) {
		char[] c = key.toCharArray();
		c[1] = win.get(c[1]);
		return new String(c);
	}
	
	private class Counter {
		HashMap<String, Integer> map;
		
		public Counter() {
			map = new HashMap<String, Integer>();
		}
		
		public Set<String> keySet() {
			return map.keySet();
		}
		
		public void add(String s) {
			int count = map.containsKey(s)? map.get(s) : 0;
			map.put(s, count+1);
		}
		
		public int deductCommon(String keyA, Counter e, String keyE) {
			if (!map.containsKey(keyA) || !e.map.containsKey(keyE)) return 0;
			int countA = map.get(keyA);
			int countE = e.map.get(keyE);
			int min = Math.min(countA, countE);
			map.put(keyA, countA - min);
			e.map.put(keyE, countE - min);
			return min;
		}
	}
}
